#include <stdio.h>

int table[1000050] = {0};
int results[1000050] = {0};

void prepare_table() {
    table[0] = 1;
    table[1] = 1;
    for (int i = 2; i < 1050; i == 2 ? (i = 3) : (i += 2)) {
        for (int n = i; n < 1000050; n += i) {
            if (i != n) table[n] = 1;
        }
    }
    int res = 0;
    for (int i = 0; i < 1000050; i++) {
        //printf("%d: %d\n", i, table[i]);
        if (i == 1 || i == 0) {
            results[i] = 0;
            continue;
        }
        if (table[i] == 0) {
            res++;
        }
        results[i] = res;
    }
}

int prime_count(int start, int end) {
    if (start > end) {
        int tmp = end;
        end = start;
        start = tmp;
    }
    return results[end] - results[start] + (table[start] ? 0 : 1);
}

int main(void) {
    prepare_table();
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", prime_count(a, b));
    }
    return 0;
}
